<?php


namespace XiaoGuai\DataStructure\LineList\DoubleCircleLinkedList;


use XiaoGuai\DataStructure\LineList\ListInterface;
use XiaoGuai\DataStructure\LineList\DoubleCircleLinkedList\DoubleCircleLinkedListNode as Node;


/**
 * 双向循环链表
 * Class DoubleLinkedList
 * @package XiaoGuai\DataStructure\LineList\DoubleCircleLinkedist
 */
class DoubleCircleLinkedList implements ListInterface
{

    /**
     * @var null|Node 头指针
     */
    protected $head = null;

    /**
     * @var null|Node 尾指针
     */
    protected $tail = null;

    /**
     * @var int 链表长度
     */
    protected $length = 0;

    /**
     * 构造一个线性表
     * ListInterface constructor.
     */
    public function __construct()
    {
        $node = new Node();
        $node->next = null;
        $node->prior = null;

        $this->head = $node;
        $this->tail = $node;
        $this->length = 0;
    }

    /**
     * 判断线性表的元素是否为空
     * @return bool
     */
    public function isEmpty(): bool
    {
        return $this->head->next === $this->head;
    }

    /**
     * 清空线性表,将线性表的数据初始化
     */
    public function clear()
    {
        $p = $this->head->next;
        while ($p !== $this->head) {
            // 删除p
            $q = $p->next;
            unset($p);
            $p = $q;
        }
        $this->head->next = null;
        $this->tail = $this->head;
        $this->length = 0;
    }

    /**
     * 返回线性表当前的元素个数
     * @return int
     */
    public function getLength(): int
    {
        return $this->length;
    }

    protected function getNodeByIndex(int $index): Node
    {
        $i = 0;
        $p = $this->head->next;

        while ($p !== $this->head && $i < $index) {
            $p = $p->next;
            $i++;
        }

        if ($p === $this->head || $i > $index) {
            throw new \Exception('overflow');
        }

        return $p;
    }

    /**
     * 根据索引获取元素
     * @param int $index
     * @return mixed
     */
    public function getElement(int $index)
    {
        $node = $this->getNodeByIndex($index);

        return $node->data;
    }

    /**
     * 查找元素的索引位置
     * @return int
     */
    public function getIndex($element): int
    {
        $i = -1;
        $p = $this->head->next;

        while ($p) {
            $i++;
            if ($p->data == $element) {
                break;
            }
            $p = $p->next;
        }

        return $p ? $i : -1;
    }

    /**
     * 在对应索引处前面插入数据元素
     * @param int $index
     * @param $element
     * @return bool
     */
    public function insertElement(int $index, $element): bool
    {
        // 判断合法性
        if ($index < 0 || $index > $this->length) {
            throw new \Exception('overflow');
        }

        // 查找插入的位置
        $i = 0;
        $p = $this->head->next;
        while ($p !== $this->head && $i < $index) {
            $p = $p->next;
            $i++;
        }

        // 准备结点
        $node = new Node();
        $node->data = $element;

        // 插入结点
        $node->prior = $p->prior;
        $node->prior->next = $node;
        $node->next = $p;
        $node->next->prior = $node;

        // 维护其他属性
        if ($p === $this->head) {
            // p指向头指针,说明从结尾处插入
            $this->tail = $node;
        }
        $this->length++;
        return true;
    }

    /**
     * 删除对应索引位置的元素
     * @param int $index
     * @return bool
     */
    public function deleteElement(int $index): bool
    {
        // 查找结点
        $p = $this->getNodeByIndex($index);

        // 删除p
        $p->next->prior = $p->prior;
        $p->prior->next = $p->next;

        // 维护其他属性
        if ($p === $this->tail) {
            // 尾指针前移
            $this->tail = $p->prior;
        }
        $this->length--;
        return true;
    }
}